package offer.day15;

public class No23entryNodeOfLoop {
    /*
     * 面试题23:链表中环的入口节点
     * 题目：如果一个链表中包括环，如何找到环的入口节点？
     * 例如：在一个1->2->3->4->5->6 链表中，环的入口节点是3
     * 			^_____________|
     *
     * 思路：1>确定链表中是否存在环。使用两个指针，一个快指针，一个慢指针。
     * 若是快指针追上了满指针证明有环的存在；若是没有追到快指针走到了末尾，则表示没有环。
     * 	   2>确定环的入口。定义两个指针，假设环有n个节点构成，则先将一个节点向前移动n个节点；
     *       然后再将两个一起移动，当第二个指针只想入口节点时，刚好第一个指针已经绕着环走了一圈了，又回到了入口节点。
     *     3>确定环中包含几个节点。1>中提到的快慢节点相遇是在环的内部，所以可以从相遇的这个节点出发向前，
     *       并开始计数，当再次回到这个节点时，就能够得到环中节点数了。
     * */

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode three = new ListNode(3);
        ListNode four = new ListNode(4);
        ListNode five = new ListNode(5);
        ListNode six = new ListNode(6);

        head.next = second;
        second.next = three;
        three.next = four;
        four.next = five;
        five.next = six;
        six.next = second;

//        showNode(head);
        ListNode node = findNode(head);
        System.out.println(node);
    }

    public static ListNode findNode(ListNode head){
        if(head==null) return null;

        ListNode slow=head.next;
        ListNode fast=slow.next;
        while(slow!=fast){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode p=head;
        while(p!=slow){
            p=p.next;
            slow=slow.next;
        }
        return p;
    }


}

